Efficient memory management is essential to the performance of complex data processing systems such as graphic imaging systems which require memory allocation for different purposes. In a graphic imaging system, such as a laser printer, data which describes an image is generated, for example, by means of a desktop publishing program. A host computer converts the image data into commands that can be used by the printer. The printer interprets these commands as descriptions of the types of graphics operations to be performed, such as draw a rectangle or draw a particular character of text. The printer also determines the associated graphic state arguments that apply to each object, such as color, font, size, and the like. The interpreted data is stored in a display list.
The printer converts the entries in the display list into data that may be used by the print engine. The display list entries are converted into pixel display values which are stored in a frame buffer to represent the shapes and colors of the objects. The values in the frame buffer are used to control the operation of the active elements in a print engine, such as a laser diode in a laser printer or a print head in an inkjet printer, to form the image. The process of converting the entries in the display list into frame buffer representations is known as rendering.
The amount of memory required to store the display list representations for a page can vary, depending on the size and complexity of the image to be printed. For example, if a page of text contains characters having an extremely small font size with minimal spacing between them, a large number of characters can appear on a single page. Each character represents a different object that forms an entry on the display list. There is no limit on the number of objects that constitute an image, thus there is no bound on the amount of memory required to hold a complete display list for a page.
To accommodate the storage needs for display list representations of images of varying complexity and size, sufficient memory must be available, in addition to memory required by the printer for other needs. While large blocks of memory could be set aside for storing display lists, this would result in an inefficient use of memory, since display lists are typically small and only occasionally require large amounts of memory. To ensure efficient use of memory, a minimum amount of memory should be set aside for storing display list entries, and an additional memory should be provided that may be dynamically allocated for storing the display list entries as needed.
Many types of dynamic memory allocation systems have been developed for various applications. In some applications, the blocks of memory that are needed for storage are of a fixed size or one of a plurality of fixed sizes. In other applications, the required block size may be variable and impossible to predict ahead of time.
For applications using fixed size blocks, blocks are typically marked as allocated in a bit map. A running pointer or index identifies the next available block in the bit map. When a block is requested, the pointer or index is updated by executing a search algorithm to search for the next available block. Bit maps are typically large, containing thousands of memory blocks. Thus, searching for a storage block in the bit map is slow and inefficient.
As an alternative to searching bit maps, linked lists have been used for linking available free memory from one block to the next block. Various algorithms are used for determining which block to allocate to meet a storage request. A "garbage collection" process is used to collect allocated memory blocks that are no longer in use and return them to the free memory list. Traditionally, linked lists have been used only for memory allocation of variable size blocks.
A technique has been proposed to use fixed size queues, each of which contains memory blocks of a particular size, in combination with a linked list of storage blocks. According to this technique, when a request for a memory block of a particular size is made, the first memory block in the queue of blocks of that particular size is allocated. The fixed size queues allow the processor to immediately find blocks of a given size without requiring a search. If the request cannot be satisfied from the queue, a search is then made of the linked list of available storage blocks. Periodically, garbage collection of all the free storage blocks present in the fixed size queues is performed, the free storage blocks are returned to the linked list of available blocks, and the fixed size queues are recreated. This periodic garbage collection requires a halt in the processing while the fixed size queues are scanned for unused blocks and recreated.
Yet another approach is described in U.S. Pat. No. 5,109,336 to Guenther et al. This approach involves combining queues of fixed size blocks and a global list of blocks of variable sizes. According to this approach, when a request cannot be satisfied from the fixed size queues, memory blocks may be allocated from a global storage containing a linked list of blocks. Pointers to available blocks in the global storage are employed, to help in searching for blocks of a particular size if the request cannot be satisfied from the queues. Continuous garbage collection is implemented to continually purge unused storage blocks from the fixed size queues. For each queue, a spill address is calculated, which determines the minimum number of blocks that are needed in the queue. The unneeded blocks are returned to the global storage. If the global storage list is not adequate, additional blocks may be obtained from an extended storage. The additional blocks are added to the global storage and are searched in the same manner as the global storage. This approach allegedly reduces the processing time required for memory allocation. However, searching for blocks in the global storage still consumes valuable processor time. Also, as the variable size blocks are allocated from various places throughout the global storage, fragmentation of the global storage results, which inhibits system performance.
For a graphic imaging system such as a printer, the more time consumed to allocate memory, the slower the printing will be. While the conventional dynamic memory allocation systems may be adequate for some applications, they consume excessive processing time and are not adequate for a graphic imaging system. Thus, there is a need for a dynamic memory allocation system that efficiently allocates memory.